package com.chixing.day02;

/**
 * 排序工具类
 * 提供了常用的排序算法，如冒泡排序、选择排序、快速排序、插入排序等
 */
public class SortUtil {
    /**
     * 冒泡排序
     *
     * @param original 要排序的原始数组
     */
    public static void bubboSort(int[] original){
        for (int i=0;i<original.length;i++) {
            for (int j = 0; j < original.length - i - 1; j++){
                if (original[j]>original[j+1]){

                    int temp;
                    temp=original[j];
                    original[j]=original[j+1];
                    original[j+1]=temp;
                }
            }
        }
    }
    public static  int getMiddle(int[] arr,int low,int high){
        int temp = arr[low];// temp = 67

        // 67，23，12，11，56，87，23，48，22，18
        // 18，23，12，11，56，87，23，48，22，18
        // 18，23，12，11，56，87，23，48，22，87
        // 18，23，12，11，56，22，23，48，22，87
        // 18，23，12，11，56，22，23，48，67，87

        while(low <high){// 0<1
            while(low <high && arr[high] > temp){//0<1  && 14>12
                high--;//h  = 0
            }
            arr[low] = arr[high]; // a[0] = a[0];
            while(low <high && arr[low] <=temp){//
                low++;
            }
            arr[high] = arr[low];//a[0] = a[0]
        }
        arr[low] = temp;//a[0] = 12
        return low;// 8
    }

    public  static void quickSort(int[] arr,int low, int high){
        if(low <high){//0,1
            //将数组一份为二
            int middle = getMiddle(arr, low, high);// arr 0,9  m = 8

            System.out.println("middle = " + middle);//m =4
            //左边进行递归 快速排序
            quickSort(arr,low,middle -1);  // arr 0,7
            //右边进行递归 快速排序
            quickSort(arr,middle + 1,high);// arr 9，9
        }
    }

    //再次封装，对外调用  12，14
    public static void quick(int[] arr){
        if(arr.length  >=2)
            quickSort(arr, 0, arr.length -1);// 0,9
    }

}
